/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import org.jheaps.Heap
import org.junit.Assert
import org.junit.Test
import java.io.*
import java.util.*

abstract class AbstractLongHeapTest {

    protected abstract fun createHeap(): Heap<Long>

    protected abstract fun createHeap(capacity: Int): Heap<Long>

    @Test
    fun test() {
        val h = createHeap()

        for (i in 0 until SIZE) {
            h.insert(i.toLong())
            Assert.assertEquals(0L, h.findMin())
            Assert.assertFalse(h.isEmpty)
            Assert.assertEquals(h.size(), (i + 1).toLong())
        }

        for (i in SIZE - 1 downTo 0) {
            Assert.assertEquals(h.findMin(), (SIZE - i - 1).toLong())
            h.deleteMin()
        }
    }

    @Test
    fun testOnlyInsert() {
        val h = createHeap()

        for (i in 0 until SIZE) {
            h.insert((SIZE - i).toLong())
            Assert.assertEquals((SIZE - i).toLong(), h.findMin())
            Assert.assertFalse(h.isEmpty)
            Assert.assertEquals(h.size(), (i + 1).toLong())
        }
    }

    @Test
    fun testInsertFromZero() {
        val h = createHeap(0)

        for (i in 0 until SIZE) {
            h.insert((SIZE - i).toLong())
            Assert.assertEquals((SIZE - i).toLong(), h.findMin())
            Assert.assertFalse(h.isEmpty)
            Assert.assertEquals(h.size(), (i + 1).toLong())
        }
    }

    /*@Test(expected = NullPointerException::class)
    fun testBadInsert() {
        val h = createHeap()
        h.insert(null)
    }*/

    @Test(expected = NoSuchElementException::class)
    fun testBadDeleteMin() {
        val h = createHeap()
        h.deleteMin()
    }

    @Test(expected = NoSuchElementException::class)
    fun testBadFindMin() {
        val h = createHeap()
        h.findMin()
    }

    @Test
    fun testOnly4() {
        val h = createHeap()

        Assert.assertTrue(h.isEmpty)

        h.insert(780L)
        Assert.assertEquals(h.size(), 1)
        Assert.assertEquals(780, h.findMin())

        h.insert(-389L)
        Assert.assertEquals(h.size(), 2)
        Assert.assertEquals(-389, h.findMin())

        h.insert(306L)
        Assert.assertEquals(h.size(), 3)
        Assert.assertEquals(-389, h.findMin())

        h.insert(579L)
        Assert.assertEquals(h.size(), 4)
        Assert.assertEquals(-389, h.findMin())

        h.deleteMin()
        Assert.assertEquals(h.size(), 3)
        Assert.assertEquals(306, h.findMin())

        h.deleteMin()
        Assert.assertEquals(h.size(), 2)
        Assert.assertEquals(579, h.findMin())

        h.deleteMin()
        Assert.assertEquals(h.size(), 1)
        Assert.assertEquals(780, h.findMin())

        h.deleteMin()
        Assert.assertEquals(h.size(), 0)

        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testSortRandomSeed1() {
        val h = createHeap()

        val generator = Random(1)

        for (i in 0 until SIZE) {
            h.insert(generator.nextLong())
        }

        var prev: Long? = null
        var cur: Long
        while (!h.isEmpty) {
            cur = h.findMin()
            h.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testSort1RandomSeed1() {
        val h = createHeap()

        val generator = Random(1)

        for (i in 0 until SIZE) {
            h.insert(generator.nextLong())
        }

        var prev: Long? = null
        var cur: Long
        while (!h.isEmpty) {
            cur = h.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testSortRandomSeed2() {
        val h = createHeap()

        val generator = Random(2)

        for (i in 0 until SIZE) {
            h.insert(generator.nextLong())
        }

        var prev: Long? = null
        var cur: Long
        while (!h.isEmpty) {
            cur = h.findMin()
            h.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testSort1RandomSeed2() {
        val h = createHeap()

        val generator = Random(1)

        for (i in 0 until SIZE) {
            h.insert(generator.nextLong())
        }

        var prev: Long? = null
        var cur: Long
        while (!h.isEmpty) {
            cur = h.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testFindMinDeleteMinSameObject() {
        val h = createHeap()

        val generator = Random(1)

        for (i in 0 until SIZE) {
            h.insert(generator.nextLong())
        }

        while (!h.isEmpty) {
            Assert.assertEquals(h.findMin(), h.deleteMin())
        }
    }

    @Test
    fun testSizeOneInitial() {
        val h = createHeap(1)

        for (i in 0..14) {
            h.insert(i.toLong())
        }

        Assert.assertEquals(15, h.size())
    }

    @Test
    fun testClear() {
        val h = createHeap()

        for (i in 0..14) {
            h.insert(i.toLong())
        }

        h.clear()
        Assert.assertEquals(0L, h.size())
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testComparator() {
        val h = createHeap()

        Assert.assertNull(h.comparator())
    }

    @Test
    @Throws(IOException::class, ClassNotFoundException::class)
    fun testSerializable() {
        var h = createHeap()

        for (i in 0..14) {
            h.insert(i.toLong())
        }

        // write
        val baos = ByteArrayOutputStream()
        val oos = ObjectOutputStream(baos)
        oos.writeObject(h)
        oos.close()
        val data = baos.toByteArray()

        // read
        val ois = ObjectInputStream(ByteArrayInputStream(data))
        val o = ois.readObject()
        ois.close()
        h = o as Heap<Long>

        for (i in 0..14) {
            Assert.assertEquals((15 - i).toLong(), h.size())
            Assert.assertEquals(i.toLong(), h.findMin())
            h.deleteMin()
        }
        Assert.assertTrue(h.isEmpty)
    }

    companion object {
        const val SIZE: Int = 100000
    }
}